package com.cuz.daileetcode;

public class Day22 {

    /***
     * 一个数组中，存在两个不同的数出现了奇数次，其他数都出现了偶数次，请找出这两个数，要求时间复杂度O(n),空间复杂度O(1)
     */
    public static int[] findTheNumberOfOddTimes(int[] ints) {
        //假设这两个数位 a 和 b
        //第一次异或的结果
        int firstRoundXOR = 0;
        for (int temp : ints) {
            firstRoundXOR = firstRoundXOR ^ temp;
        }
        //其他数都出现偶数组，交换律，自己异或自己为0 所以firstRoundXOR=a^b
        //题目说了两个不同的数 所以a!=b 所以firstRoundXOR！=0
        //firstRoundXOR！=0说明firstRoundXOR每一位并不是全为0，所以至少存在一位是1
        //假设为1的哪一位是第2位，那么我们可以把数组分为两种，第2位为0的，第2不为0的
        //a和b肯定位于这两个部分
        //假如数组中的数是  10101，10101，1011，1011，100010（a），100100（b）
        //为什么说a和b肯定位于这两个部分（a，b在第二位不同） 如果a，b第二位相同那么firstRoundXOR第二位肯定为0
        //（用无进位相加的思想看，第二位，偶数个1或者偶数个0相加，那么第二位一定为0，和我们的假设相违背）
        //接下来我们只要让 第二位为0的数进行异或=>也就是10101^10101^100100(b)就可以得到b
        //第二位不为0的数异或可以得到a
        //但是firstRoundXOR=a^b,那么直接firstRoundXOR异或b就可以得到a

        //现在的问题是我们怎么知道firstRoundXOR 哪一位不为0
        //mostRightOne 是firstRoundXOR最右侧的1，为什么
        int mostRightOne = firstRoundXOR & (~firstRoundXOR + 1);
        //假如firstRoundXOR为  1010110
        //那么~firstRoundXOR为 0101001
        //~firstRoundXOR+1为  0101010
        //firstRoundXOR&(~firstRoundXOR+1) 就是
        //  1010110
        //& 0101010
        //= 0000010
        //ok 我们得到第二位的1了=>mostRightOne
        //如果数组中的数和mostRightOne与操作等于0代表第二位为0
        //反之第二位为1
        //让所有第二位为1（或者为0）的数异或，得到a和b其中一个
        int oneResult = 0;
        for (int temp : ints) {
            //第二为1
            if ((mostRightOne & temp) == 1) {
                oneResult = oneResult ^ temp;
            }
        }
        //oneResult 是a或者b，firstRoundXOR是a^b ，oneResult ^ firstRoundXOR是我们的另外一个数了
        return new int[]{oneResult, oneResult ^ firstRoundXOR};
    }
}
